package com.dy.回溯算法.全排列;

import java.util.ArrayList;
import java.util.List;

/*
全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
 */
public class Solution {
    public static  List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length==0)return res;
        return permutation(nums,0);

    }
    //得到从n开始往后的排列,插入
    private static  List<List<Integer>> permutation(int[] nums,int n){
        List<List<Integer>> list = new ArrayList<>();
        if(n==nums.length-1){
            List<Integer> tmp = new ArrayList<>();
            tmp.add(nums[n]);
            list.add(tmp);
            return list;
        }

        list = permutation(nums,n+1);
        List<List<Integer>> res = new ArrayList<>();
        for(List<Integer> l1:list){
            for(int j =0;j<=l1.size();j++){
                List<Integer> tmp = new ArrayList<>();
                tmp.addAll(l1);
                tmp.add(j,nums[n]);
                res.add(tmp);
            }
        }
        return res;


    }
    static List<List<Integer>> list = new ArrayList<>();
    public static  List<List<Integer>> permute2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length==0)return res;
        permutation2(nums,0);
        return list;

    }
    //得到从n开始往后的排列
    private static void  permutation2(int[] nums,int n){

        if(n==nums.length-1){
            List<Integer> tmp = new ArrayList<>();
            for(int num:nums){
                tmp.add(num);
            }
            list.add(tmp);

        }

        for(int i=n;i<nums.length;i++){
            int tmp = nums[n];
            nums[n]=nums[i];
            nums[i]=tmp;
            permutation2(nums,n+1);
            tmp = nums[n];
            nums[n]=nums[i];
            nums[i]=tmp;

        }



    }
}
